#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define MaxSize 50
typedef int ElemType;
typedef struct SeqList{
    ElemType data[MaxSize];
    int length;
}SeqList;
// 初始化数组：给数组中填充元素
void initList(SeqList &S,int length){
    S.length = length;
    srand(time(NULL));// 生成随机数
    for(int i=0;i<S.length;i++){
        S.data[i] = rand()%100;
    }
}
// 遍历数组中的数据
void printList(SeqList S){
    for (int i = 0; i < S.length; ++i) {
        printf("%d ",S.data[i]);
    }
    printf("\n");
}
// 插入排序：从小到大
void InsertSort(ElemType E[],int length){
    ElemType tmp;
    // 默认第1个元素是已经排好序的，因此下标从1开始
    for(int i=1;i<length;i++){
        if(E[i] < E[i-1]){ // 当前结点小于前驱元素
            tmp = E[i]; // 临时保存当前结点的数据
            int j;
            // 将前面所有小于tmp值的元素都后移一位
            for(j=i-1;j>=0 && E[j]> tmp;j--){
                E[j+1] = E[j];
            }
            E[j+1] = tmp; // 复制数据到当前结点
        }
    }
}
int main() {
    SeqList S;
    initList(S,10);
    printList(S);
    InsertSort(S.data,S.length);
    printList(S);
    return 0;
}
